//https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
        {
            return ret;
        }

        queue<TreeNode*> q;
        q.push(root);
        bool flagLeft = true;
        while (!q.empty())
        {
            deque<int> dq;
            int size = q.size();
            for (int i = 0; i < size; ++i)
            {
                TreeNode* top = q.front();
                if (flagLeft)
                {
                    dq.push_back(top->val);
                }
                else
                {
                    dq.push_front(top->val);
                }
                q.pop();

                if (top->left)
                    q.push(top->left);
                if (top->right)
                    q.push(top->right);
            }
            ret.emplace_back(vector<int>(dq.begin(), dq.end()));
            flagLeft = !flagLeft;
        }

        return ret;
    }
};